from functools import lru_cache

class Solution:
    def shoppingOffers(self, price: list, special: list, needs: list) -> int:
        n = len(price)
        
        # 过滤掉不划算的礼包
        filtered_special = []
        for s in special:
            # 计算礼包中物品的单独购买总价
            sum_alone = sum(s[i] * price[i] for i in range(n))
            # 如果礼包价格低于单独购买总价，且礼包中的物品数量不超过需求，则保留该礼包
            if s[-1] < sum_alone and all(s[i] <= 10 for i in range(n)):
                filtered_special.append(s)
        
        # 使用元组表示需求状态，以便进行缓存
        @lru_cache(maxsize=None)
        def dfs(cur_needs):
            # 计算单独购买所有物品的总价
            min_cost = sum(cur_needs[i] * price[i] for i in range(n))
            
            # 尝试每个礼包
            for s in filtered_special:
                # 检查礼包中的物品数量是否超过当前需求
                can_use = True
                for i in range(n):
                    if s[i] > cur_needs[i]:
                        can_use = False
                        break
                if can_use:
                    # 计算使用礼包后的新需求
                    new_needs = tuple(cur_needs[i] - s[i] for i in range(n))
                    # 递归计算新需求的最低价格
                    cost = s[-1] + dfs(new_needs)
                    # 更新最低价格
                    if cost < min_cost:
                        min_cost = cost
            return min_cost
        
        return dfs(tuple(needs))    